/**
 * 5种操作：
 * 1 区间查询给定权值的排名
 * 2 区间查询第k小的权值
 * 3 单点修改
 * 4 区间查询前驱
 * 5 区间查询后继
 * 
 * 如果不考虑区间，所有操作都是基于平衡排序树的。
 * 现在考虑区间，可以考虑线段树套平衡树
 * 对线段树的每个节点所对应的区间，建一个排序树
 * 然后只需要利用线段树框架进行分治即可
 * 
 * 考虑线段树的经典思路：
 * 对于操作1：如果能够很快知道左区间比k小的权值数量，同时很快知道右区间比k小的权值数量，
 * 显然可以立刻知道整个区间比k小的权值数量，也就得到了权值k的排名
 * 如果当前考虑的区间是一个完整的线段树节点，通过平衡树能够很快知道该区间内比k小的权值数量
 * 对于操作4、5，同理。如果能够很快知道左、右区间各自的针对k的前驱后继，显然能够立刻知道整个区间内针对k的前驱后继。
 * 对操作3，是线段树单点修改的基本操作，不过不要pushUp，肯定超时，拿到原始值以后直接在二叉树上操作即可。
 * 对于操作2：可以考虑二分查找，对于给定的mid，利用操作1查询其排名，二分区间逼近k即可
 */
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>

using llt = long long;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vll = vector<llt>;

template<typename T>
void input(vector<T>&v, int n){
    v.assign(n + 1, {});
    for(int i=1;i<=n;++i) cin >> v[i];
}

template<typename T>
istream & operator >> (istream & is, vector<T> & v){
    for(auto & i : v) is >> i;
    return is;
}

llt const INF = 0x1F2F3F4F5F6F7F8F;
llt const NINF = -INF;
llt const MOD = 201314;


struct PBDS_BST{ // pbds的红黑树实现二叉排序树

using T = int;
using key_t = pair<T, int>; // 加时间戳，可以处理相同的键值
using value_t = int;

__gnu_pbds::tree<
    key_t, value_t, std::less<key_t>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update
>shu;

/// 插入键值对，k是键，timestamp是时间戳
void insert(const T & k, int timestamp, const value_t & v = 0){
    this->shu.insert({{k, timestamp}, v});
}

/// 删除键，保证k至少存在一个
void erase(const T & k){
    auto it = this->shu.lower_bound({k, 0});
    assert(it->first.first == k);
    this->shu.erase(it);
}

/// 查询k在树中的排名，最小的数排名为1
/// k可以不存在于树中，此时为假设k在树中的排名
/// 假设k存在于树中，令time为负数，则返回第一个k在树中的排名
/// time为无穷大则返回最后一个k在树中的排名
int rank(const T & k, int time)const{
    auto ret = this->shu.order_of_key({k, time});
    return ret + 1;
}

/// 取出排名为第sn的键，最小的数为第1名
T select(int sn)const{
    assert(0 < sn && sn <= this->shu.size());
    auto it = this->shu.find_by_order(sn - 1);
    return it->first.first;
}

/// 求k的前驱，即比k小的最大的键，保证有
T pred(const T & k)const{
    auto it = this->shu.lower_bound({k, 0});
    assert(it != this->shu.begin());
    --it;
    return it->first.first;
}

/// 求k的后继，即比k大的最小的键，保证有
/// 需要传一个比目前时间戳更大的数
T succ(const T & k, int largestStamp = INT32_MAX)const{
    auto it = this->shu.upper_bound({k, largestStamp});
    assert(it != this->shu.end());
    return it->first.first;
}

int size()const{return this->shu.size();}

/// 返回最小值，保证树不为空
T min()const{return this->shu.begin()->first.first;}

/// 返回最大值，保证树不为空
T max()const{return (--this->shu.end())->first.first;}

};


struct SegTree{ // 线段树带延迟

using llt = long long;

int N;

using value_type = PBDS_BST;
vector<value_type> data; // 线段树

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    // assert(0);
    value_type ret(ls);
    for(auto it=++rs.shu.begin(),et=--rs.shu.end();it!=et;++it){
        ret.insert(it->first.first, it->first.second);
    }
    return ret;
}

/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
}

/// 这个函数不用动
void build() {
    _build(1, 1, N);
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 几乎不用动
void _build(int t, int s, int e) {
    if(s == e) {
        int x; cin >> x;
        // data[t] = value_type(x); // 注意提供value_type的初始化
        data[t].insert(INT_MIN, INT_MIN);
        data[t].insert(x, s);
        data[t].insert(INT_MAX, INT_MAX);
        return; 
    }
    int mid = (s + e) >> 1;
    _build(lson(t), s, mid);
    _build(rson(t), mid + 1, e);
    _pushUp(t);
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0;
    return VALUE0;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}

/// [a, b]区间比k小的数有多少个
int _countLT(int t, int s, int e, int a, int b, int k){
    if(a <= s and e <= b){
        int x = data[t].rank(k, -1);
        return x - 1 - 1; // 要减掉哨兵
    }

    int mid = (s + e) >> 1;
    int ans = 0;
    if(a <= mid) ans += _countLT(lson(t), s, mid, a, b, k);
    if(mid < b) ans += _countLT(rson(t), mid + 1, e, a, b, k);
    return ans;
}

int _pred(int t, int s, int e, int a, int b, int k){
    if(a <= s and e <= b){
        return data[t].pred(k);
    }

    int mid = (s + e) >> 1;
    int ans = -1;
    if(a <= mid){
        auto tmp = _pred(lson(t), s, mid, a, b, k);
        if(-1 == ans or ans < tmp) ans = tmp;
    }
    if(mid < b){
        auto tmp = _pred(rson(t), mid + 1, e, a, b, k);
        if(-1 == ans or ans < tmp) ans = tmp;
    }
    return ans;
}

int _succ(int t, int s, int e, int a, int b, int k){
    if(a <= s and e <= b){
        return data[t].succ(k);
    }

    int mid = (s + e) >> 1;
    int ans = -1;
    if(a <= mid){
        auto tmp = _succ(lson(t), s, mid, a, b, k);
        if(-1 == ans or ans > tmp) ans = tmp;
    }
    if(mid < b){
        auto tmp = _succ(rson(t), mid + 1, e, a, b, k);
        if(-1 == ans or ans > tmp) ans = tmp;
    }
    return ans;
}

PBDS_BST::key_t _modify(int t, int s, int e, int pos, int k){
    if(s == e){
        auto it = ++data[t].shu.begin();
        auto p = it->first;
        data[t].shu.erase(it);
        data[t].insert(k, s);
        return p;
    }

    int mid = (s + e) >> 1;
    if(pos <= mid){
        auto p = _modify(lson(t), s, mid, pos, k);
        auto it = data[t].shu.find(p);
        assert(it != data[t].shu.end());
        data[t].shu.erase(it);
        data[t].insert(k, pos);
        return p;
    }

    auto p = _modify(rson(t), mid + 1, e, pos, k);
    auto it = data[t].shu.find(p);
    assert(it != data[t].shu.end());
    data[t].shu.erase(it);
    data[t].insert(k, pos);
    return p;
}

/// 查询权值k的排名
int rank(int a, int b, int k){
    int x = _countLT(1, 1, N, a, b, k);
    return x + 1;
}

/// 查询[a,b]区间内第k小的权值
int select(int a, int b, int k){
    int left = 1, right = 2E9, mid;
    do{
        mid = (left + right) >> 1;
        if(_countLT(1, 1, N, a, b, mid) < k) left = mid + 1;
        else right = mid - 1;
    }while(left <= right);
    /// right是count小于k的最后一个数，保证有解，所以right前面有k-1个数, right是第k名
    // cout << "right = " << right << endl;
    return right;
}

int pred(int a, int b, int k){
    return _pred(1, 1, N, a, b, k);
}

int succ(int a, int b, int k){
    return _succ(1, 1, N, a, b, k);
}

void modify(int pos, int k){
    _modify(1, 1, N, pos, k);
}

}St;

int N, Q;

void work(){
    cin >> N >> Q;
    St.init(N);
    St.build();
    for(int cmd,a,b,k,q=1;q<=Q;++q){
        cin >> cmd >> a >> b;
        if(1 == cmd){
            cin >> k;
            auto ans = St.rank(a, b, k);
            cout << ans << "\n";
        }else if(2 == cmd){ 
            cin >> k;
            auto ans = St.select(a, b, k);
            cout << ans << "\n";
        }else if(3 == cmd){
            St.modify(a, b);
        }else if(4 == cmd){
            cin >> k;
            auto ans = St.pred(a, b, k);
            cout << ans << "\n";
        }else if(5 == cmd){
            cin >> k;
            auto ans = St.succ(a, b, k);
            cout << ans << "\n";
        }else{
            assert(0);
        }
    }
    return;
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase; 
    while(nofkase--) work();    
    return 0;
}
